{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Spaces Cleaning Robot Cleaned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfCleanRooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扫地机器人清扫过的空间个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个房间用一个<strong>从 0 开始索引</strong>的二维二进制矩阵 <code>room</code> 表示，其中 <code>0</code> 表示<strong>空闲</strong>空间， <code>1</code> 表示放有<strong>物体</strong>的空间。在每个测试用例中，房间左上角永远是空闲的。</p>\n",
    "\n",
    "<p>一个扫地机器人面向右侧，从左上角开始清扫。机器人将一直前进，直到抵达房间边界或触碰到物体时，机器人将会<strong>顺时针</strong>旋转 90 度并重复以上步骤。初始位置和所有机器人走过的空间都会被它<strong>清扫干净</strong>。</p>\n",
    "\n",
    "<p>若机器人持续运转下去，返回被<strong>清扫干净</strong>的空间数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong><br />\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/11/01/image-20211101204703-1.png\" style=\"width: 250px; height: 242px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> room = [[0,0,0],[1,1,0],[0,0,0]]\n",
    "<strong>输出:</strong> 7\n",
    "<strong>解释:</strong>\n",
    "机器人清理了位于 (0, 0)、 (0, 1) 和 (0, 2) 的空间。\n",
    "机器人位于房间边界，所以它顺时针旋转 90 度，现在面向下。\n",
    "机器人清理了位于 (1, 2) 和 (2, 2) 的空间。\n",
    "机器人位于房间边界，所以它顺时针旋转 90 度，现在面向左。\n",
    "机器人清理了位于 (2, 1) 和 (2, 0) 的空间。\n",
    "机器人已清理了所有 7 处空闲空间，所以返回 7。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong><br />\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/11/01/image-20211101204736-2.png\" style=\"width: 250px; height: 245px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> room = [[0,1,0],[1,0,0],[0,0,0]]\n",
    "<strong>输出t:</strong> 1\n",
    "<strong>解释:</strong>\n",
    "机器人清理了位于 (0, 0) 的空间。\n",
    "机器人触碰到了物体，所以它顺时针旋转 90 度，现在面向下。\n",
    "机器人触碰到了物体，所以它顺时针旋转 90 度，现在面向左。\n",
    "机器人位于房间边界，所以它顺时针旋转 90 度，现在面向上。\n",
    "机器人位于房间边界，所以它顺时针旋转 90 度，现在面向右。\n",
    "机器人回到了起始位置。\n",
    "机器人清理了 1 处空间，所以返回 1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == room.length</code></li>\n",
    "\t<li><code>n == room[r].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 300</code></li>\n",
    "\t<li><code>room[r][c]</code> 只会是 <code>0</code> 或 <code>1</code> 。</li>\n",
    "\t<li><code>room[0][0] == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-spaces-cleaning-robot-cleaned](https://leetcode.cn/problems/number-of-spaces-cleaning-robot-cleaned/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-spaces-cleaning-robot-cleaned](https://leetcode.cn/problems/number-of-spaces-cleaning-robot-cleaned/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,0],[1,1,0],[0,0,0]]', '[[0,1,0],[1,0,0],[0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        room[0][0] = -1\n",
    "        index = 0\n",
    "        tryTimes = 0\n",
    "        cnt = 1\n",
    "        x, y = 0, 0\n",
    "        m, n = len(room), len(room[0])\n",
    "        while True:\n",
    "            if tryTimes == 5:   return cnt\n",
    "            X, Y = x + direction[index][0], y + direction[index][1]\n",
    "            if 0 <= X < m and 0 <= Y < n:\n",
    "                if room[X][Y] == -2:    return cnt\n",
    "                elif room[X][Y] == 0:\n",
    "                    cnt += 1\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -1\n",
    "                elif room[X][Y] == -1:\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -2\n",
    "                else:\n",
    "                    tryTimes += 1\n",
    "                    index = (index + 1) % 4\n",
    "            else:\n",
    "                tryTimes += 1\n",
    "                index = (index + 1) % 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        m, n = len(room), len(room[0])\n",
    "        vis, state = set(), set()\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "        \n",
    "        x, y, d = 0, 0, 0\n",
    "        \n",
    "        while 1:\n",
    "            if (x, y, d) in state:\n",
    "                break\n",
    "            vis.add((x, y))\n",
    "            state.add((x, y, d))\n",
    "            dx, dy = dir[d]\n",
    "            nx, ny = x + dx, y + dy \n",
    "            if not valid(nx, ny) or room[nx][ny] == 1:\n",
    "                d = (d + 1) % 4\n",
    "            else:\n",
    "                x += dx \n",
    "                y += dy \n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        room[0][0] = -1\n",
    "        index = 0\n",
    "        tryTimes = 0\n",
    "        cnt = 1\n",
    "        x, y = 0, 0\n",
    "        m, n = len(room), len(room[0])\n",
    "        while True:\n",
    "            if tryTimes == 5:   return cnt\n",
    "            X, Y = x + direction[index][0], y + direction[index][1]\n",
    "            if 0 <= X < m and 0 <= Y < n:\n",
    "                if room[X][Y] == -2:    return cnt\n",
    "                elif room[X][Y] == 0:\n",
    "                    cnt += 1\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -1\n",
    "                elif room[X][Y] == -1:\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -2\n",
    "                else:\n",
    "                    tryTimes += 1\n",
    "                    index = (index + 1) % 4\n",
    "            else:\n",
    "                tryTimes += 1\n",
    "                index = (index + 1) % 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        m, n = len(room), len(room[0])\n",
    "        POS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        x, y, z = 0, 0, 0\n",
    "        has = set()\n",
    "        while (x,y,z) not in has:\n",
    "            has.add((x,y,z))\n",
    "            nx, ny = x + POS[z][0], y + POS[z][1]\n",
    "            if 0 <= nx < m and 0 <= ny < n and room[nx][ny] == 0:\n",
    "                x, y = nx, ny\n",
    "            else:\n",
    "                z = (z + 1) % 4\n",
    "        return len(set((i,j) for i,j,z in has))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        room[0][0] = -1\n",
    "        index = 0\n",
    "        tryTimes = 0\n",
    "        cnt = 1\n",
    "        x, y = 0, 0\n",
    "        m, n = len(room), len(room[0])\n",
    "        while True:\n",
    "            if tryTimes == 5:   return cnt\n",
    "            X, Y = x + direction[index][0], y + direction[index][1]\n",
    "            if 0 <= X < m and 0 <= Y < n:\n",
    "                if room[X][Y] == -2:    return cnt\n",
    "                elif room[X][Y] == 0:\n",
    "                    cnt += 1\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -1\n",
    "                elif room[X][Y] == -1:\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -2\n",
    "                else:\n",
    "                    tryTimes += 1\n",
    "                    index = (index + 1) % 4\n",
    "            else:\n",
    "                tryTimes += 1\n",
    "                index = (index + 1) % 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        room[0][0] = -1\n",
    "        index = 0\n",
    "        tryTimes = 0\n",
    "        cnt = 1\n",
    "        x, y = 0, 0\n",
    "        m, n = len(room), len(room[0])\n",
    "        while True:\n",
    "            if tryTimes == 5:   return cnt\n",
    "            X, Y = x + direction[index][0], y + direction[index][1]\n",
    "            if 0 <= X < m and 0 <= Y < n:\n",
    "                if room[X][Y] == -2:    return cnt\n",
    "                elif room[X][Y] == 0:\n",
    "                    cnt += 1\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -1\n",
    "                elif room[X][Y] == -1:\n",
    "                    tryTimes, x, y, room[X][Y] = 0, X, Y, -2\n",
    "                else:\n",
    "                    tryTimes += 1\n",
    "                    index = (index + 1) % 4\n",
    "            else:\n",
    "                tryTimes += 1\n",
    "                index = (index + 1) % 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        m, n, POS, x, y, z, has = len(room), len(room[0]), ((0, 1), (1, 0), (0, -1), (-1, 0)), 0, 0, 0, set()\n",
    "        while (x,y,z) not in has:\n",
    "            has.add((x,y,z))\n",
    "            nx, ny = x + POS[z][0], y + POS[z][1]\n",
    "            if 0 <= nx < m and 0 <= ny < n and room[nx][ny] == 0: x, y = nx, ny\n",
    "            else: z = (z + 1) % 4\n",
    "        return len(set((i,j) for i,j,z in has))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        m, n = len(room), len(room[0]) \n",
    "        vis = set() \n",
    "        #vis.add((0,0,0))\n",
    "        dx = [0,1,0,-1]\n",
    "        dy = [1,0,-1,0]\n",
    "        Q = deque([(0,0,0)])\n",
    "        mark = [[0]*n for _ in range(m)]\n",
    "        ans = 0\n",
    "        while Q:\n",
    "            d, x, y = Q.popleft()\n",
    "            if (d, x, y) in vis:\n",
    "                continue \n",
    "            vis.add((d,x,y))\n",
    "            if mark[x][y] == 0:\n",
    "                ans += 1\n",
    "                mark[x][y] = 1\n",
    "            nx, ny = x + dx[d], y + dy[d]\n",
    "            if 0<=nx<m and 0<=ny<n and room[nx][ny] == 0:\n",
    "                Q.append((d, nx, ny))\n",
    "            else:\n",
    "                d = (d+1) % 4 \n",
    "                Q.append((d, x, y)) \n",
    "        return ans \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        x=0\n",
    "        y=0\n",
    "        m=len(room)\n",
    "        cnt=1\n",
    "        n=len(room[0])\n",
    "        room[x][y]=2\n",
    "        step=1\n",
    "        while step<2*m*n:\n",
    "            f=0\n",
    "            while y+1<n and room[x][y+1]!=1:\n",
    "                y=y+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x+1<m and room[x+1][y]!=1:\n",
    "                x=x+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while y-1>=0 and room[x][y-1]!=1:\n",
    "                y=y-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x-1>=0 and room[x-1][y]!=1:\n",
    "                x=x-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "          #  print(room)\n",
    "          #  print(cnt)\n",
    "            if f==0:\n",
    "                break\n",
    "        print(room)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        x=0\n",
    "        y=0\n",
    "        m=len(room)\n",
    "        cnt=1\n",
    "        n=len(room[0])\n",
    "        room[x][y]=2\n",
    "        step=1\n",
    "        while step<5*m*n:\n",
    "            f=0\n",
    "            while y+1<n and room[x][y+1]!=1:\n",
    "                y=y+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x+1<m and room[x+1][y]!=1:\n",
    "                x=x+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while y-1>=0 and room[x][y-1]!=1:\n",
    "                y=y-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x-1>=0 and room[x-1][y]!=1:\n",
    "                x=x-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "          #  print(room)\n",
    "          #  print(cnt)\n",
    "            if f==0:\n",
    "                break\n",
    "        print(room)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        x=0\n",
    "        y=0\n",
    "        m=len(room)\n",
    "        cnt=1\n",
    "        n=len(room[0])\n",
    "        room[x][y]=2\n",
    "        step=1\n",
    "        while step<m*n+5:\n",
    "            f=0\n",
    "            while y+1<n and room[x][y+1]!=1:\n",
    "                y=y+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x+1<m and room[x+1][y]!=1:\n",
    "                x=x+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while y-1>=0 and room[x][y-1]!=1:\n",
    "                y=y-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x-1>=0 and room[x-1][y]!=1:\n",
    "                x=x-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "          #  print(room)\n",
    "          #  print(cnt)\n",
    "            if f==0:\n",
    "                break\n",
    "        print(room)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        x=0\n",
    "        y=0\n",
    "        m=len(room)\n",
    "        cnt=1\n",
    "        n=len(room[0])\n",
    "        room[x][y]=2\n",
    "        step=1\n",
    "        while step<3*m*n:\n",
    "            f=0\n",
    "            while y+1<n and room[x][y+1]!=1:\n",
    "                y=y+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x+1<m and room[x+1][y]!=1:\n",
    "                x=x+1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while y-1>=0 and room[x][y-1]!=1:\n",
    "                y=y-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "            while x-1>=0 and room[x-1][y]!=1:\n",
    "                x=x-1\n",
    "                f=1\n",
    "                step+=1\n",
    "                if room[x][y]==0:\n",
    "                    cnt+=1\n",
    "                    room[x][y]=2\n",
    "          #  print(room)\n",
    "          #  print(cnt)\n",
    "            if f==0:\n",
    "                break\n",
    "        print(room)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        dirs=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        m=len(room)\n",
    "        n=len(room[0])\n",
    "        vis=set()\n",
    "        vis.add((0,0,0))\n",
    "        s=set()\n",
    "        s.add((0,0))\n",
    "        def dfs(x,y,d):\n",
    "            res=0\n",
    "            dx=dirs[d][0]\n",
    "            dy=dirs[d][1]\n",
    "            while 0<=x+dx<m and 0<=y+dy<n and room[dx+x][dy+y]==0 :\n",
    "                if (x+dx,y+dy,d) not in vis:\n",
    "                    vis.add((x+dx,y+dy,d))\n",
    "                    if (x+dx,y+dy) not in s:\n",
    "                        res+=1\n",
    "                        s.add((x+dx,y+dy))\n",
    "                    x+=dx\n",
    "                    y+=dy\n",
    "                else :\n",
    "                    return res\n",
    "            if (x,y,(d+1)%4) not in vis:\n",
    "                vis.add((x,y,(d+1)%4))\n",
    "                res+=dfs(x,y,(d+1)%4)\n",
    "            return res\n",
    "        return 1+dfs(0,0,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        m, n = len(room), len(room[0])\n",
    "        dirs = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        vis = set()\n",
    "        ans = set()\n",
    "        def dfs(x, y, d):\n",
    "            if (x, y, d) in vis:\n",
    "                return\n",
    "            ans.add((x, y))\n",
    "            vis.add((x, y, d))\n",
    "            i = x + dirs[d][0]\n",
    "            j = y + dirs[d][1]\n",
    "            if 0 <= i < m and 0 <= j < n and room[i][j] == 0:\n",
    "                dfs(i, j, d)\n",
    "            else:\n",
    "                dfs(x, y, (d + 1) % 4)\n",
    "        dfs(0, 0, 0)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # dfs\n",
    "DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCleanRooms(self, room: List[List[int]]) -> int:\n",
    "        m, n, ans, visited = len(room), len(room[0]), set(), set()\n",
    "        def dfs(x, y, idx):\n",
    "            if (x, y, idx) in visited:\n",
    "                return\n",
    "\n",
    "            ans.add((x, y))\n",
    "            visited.add((x, y, idx))\n",
    "            if 0 <= (nx := x + DIRS[idx][0]) < m and 0 <= (ny := y + DIRS[idx][1]) < n and not room[nx][ny]:\n",
    "                dfs(nx, ny, idx)\n",
    "            else:\n",
    "                dfs(x, y, (idx + 1) % 4)\n",
    " \n",
    "\n",
    "        dfs(0, 0, 0)\n",
    "        return len(ans)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
